//题目:
// 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
// 你可以按 任何顺序 返回答案。

// 示例 1：
// 输入：n = 4, k = 2
// 输出：
// [
//   [2,4],
//   [3,4],
//   [2,3],
//   [1,2],
//   [1,3],
//   [1,4],
// ]

// 示例 2：
// 输入：n = 1, k = 1
// 输出：[[1]]

#include<iostream>
#include<vector>

using namespace std;

//代码:
class Solution 
{
    int n,k;
    vector<bool> flags;
    vector<vector<int>> ret;
public:
    void Combine(vector<int>& v,int pos)
    {
        if(k==v.size())
        {
            ret.push_back(v);
            return;
        }
    
        //第pos个位置选取哪个元素
        for(int j=pos;j<=n;j++)
        {
            if(flags[j]==false)
            {
                flags[j]=true;
                v.push_back(j);
                Combine(v,j+1);
                //回溯
                flags[j]=false;
                v.pop_back();
            }
        }
    }
    vector<vector<int>> combine(int _n, int _k) 
    {
        n=_n,k=_k;
        flags.resize(n+1,false);
        
        vector<int> arr;
        Combine(arr,1);
        return ret;
    }
};